package main

import "fmt"

func quickSort(nums []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partition(nums, lo, hi)
	quickSort(nums, lo, p-1)
	quickSort(nums, p+1, hi)
}

func partition(nums []int, lo, hi int) int {
	j := lo - 1
	for i := lo; i < hi; i++ {
		if nums[i] < nums[hi] {
			j++
			nums[j], nums[i] = nums[i], nums[j]
		}
	}
	nums[j+1], nums[hi] = nums[hi], nums[j+1]
	return j + 1
}

func main() {
	nums := []int{3, 2, 4, 1}
	quickSort(nums, 0, len(nums)-1)
	fmt.Println(nums)
}
